Binary Search Tree (BST) Operations cheatsheet

根據昨天的簡單 leetcode 練習
今天走一點學術風格
把幾個 operations 整理一下。

Search by recursive

TREE-SEARCH(x, k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, k)
    else return TREE-SEARCH(x. right, k)

Search by iterative

ITERATIVE-TREE-SEARCH(x, k)
    while x != NIL and k != x.key
        if k < x.key
            x = x.left
        else
            x = x.right
    return x

不管是哪種方法，只要記得 BST 的基本特性（左小右大），都可以很直覺的想出上面的 code

Tree Minimum / Maxmum

TREE-MINIMUM(x)
    while x.left != NIL
        x = x.left
    return x

TREE-MAXMUM(x)
    while x.right != NIL
        x = x.right
    return x

Find the Next Larger Element

TREE-SUCCESSOR(x)
    if x.left != NIL
        return TREE-MINIMUM(x.right)
    y = x.p
    while y != NIL and x == y.right
        x = y
        y = y.p
    return y

Insertion

TREE-INSERT(T, z)
    y = NIL
    x = T.root
    while x != NIL
        y = x
        if z.key < x.key
            x = x.left
        else
            x = x.right
    z.p = y
    if y == NIL
        T.root = z
    else if z.key < y.key
        y.left = z
    else
        y.right = z

Transplant Routine

當點被移除時，將其他的點轉移上來。看圖：

TRANSPLANT(T, u, v)
    if u.p == NIL
        T.root = v
    else if u == u.p.left
        u.p.left = v
    else
        u.p.right = v
    if v != NIL
        v.p = u.p

Delete a key/Node

TREE-DELETE(T, z)
    if z.left == NIL
        TRANSPLANT(T, z, z.right)
    else if z.right == NIL
        TRANSPLANT(T, z, z.left)
    else
        y = TREE-MINIMUM(z.right)
        if y.p != z
            TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y